\documentclass{article}

\usepackage{arxiv}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc} %\usepackage{ae} \usepackage{aecompl} % use 8-bit T1 fonts
\usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography
\usepackage{lipsum}

\usepackage{bbm}           % allows to write the "blackboard 1" symbol \mathbbm{1}
\usepackage{amsthm}
\usepackage{amsmath,amssymb}
\usepackage[]{algorithm2e}

\usepackage{xfrac}
\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.14}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}

%\usepackage{graphicx}
%\usepackage{caption}
%\usepackage{subcaption}

\hyphenation{block-chain}
\hyphenation{demo-cracy}

\newcommand{\R}{\mathbb{R}_{\geq 0}}
\newcommand{\eps}{\varepsilon}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\st}{stop}
\DeclareMathOperator{\ins}{Insert}
\DeclareMathOperator{\maxpscore}{MaxPscore}
\DeclareMathOperator{\maxprescore}{MaxPscore}
\DeclareMathOperator{\maxscore}{MaxScore}
\DeclareMathOperator{\interval}{FindInterval}
\DeclareMathOperator{\MMS}{MMS}
\DeclareMathOperator{\lazy}{LazyMMS}
\DeclareMathOperator{\phragmen}{seqPhragmen}
\DeclareMathOperator{\maxphragmen}{maxPhragmen}
\DeclareMathOperator{\phragmms}{Phragmms}
%\DeclareMathOperator{\balanced}{BalPhragmms}
\DeclareMathOperator{\LSPJR}{LS-Phragmms}
\DeclareMathOperator{\local}{LS-Phragmms}
%\DeclareMathOperator{\balancing}{balancing}
\DeclareMathOperator{\bal}{Bal}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\score}{score}
\DeclareMathOperator{\pscore}{pscore}
\DeclareMathOperator{\prescore}{pscore}
\DeclareMathOperator{\slack}{slack}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem*{lemma*}{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{heuristic}{Heuristic}

%\title{Validator Selection in Nominated Proof of Stake}
\title{A verifiably secure and proportional committee election rule}
\author{
  Alfonso Cevallos \\
  Web 3.0 Technologies Foundation\\
  Zug, Switzerland \\
  \texttt{alfonso@web3.foundation} \\
  %% examples of more authors
   \And
 Alistair Stewart \\
  Web 3.0 Technologies Foundation\\
  Zug, Switzerland \\
  \texttt{alistair@web3.foundation} \\
  %% \AND
  %% Coauthor \\
  %% Affiliation \\
  %% Address \\
  %% \texttt{email} \\
}

\begin{document}
\maketitle

\input{abstract.tex}

\keywords{computational social choice \and approval-based committee election \and approximation algorithms \and proof-of-stake \and blockchain}

%\newpage

\input{intro.tex}

\input{preliminaries.tex}

\input{complexity.tex}

\input{heuristic.tex}

\input{approx315.tex}

\input{verifiable.tex}

\input{implementation.tex}

\input{conclusion.tex}

\bibliographystyle{abbrv}  
\bibliography{references} 

\appendix

\input{local.tex}

\input{balanced.tex}

\input{flow.tex}

\input{algorithms}

\input{lazymms.tex}

\input{proofs.tex}



\end{document}

TO DO:

- Possibly a section with further details on NPoS, such as the payouts that provide nominators with incentives to shift preferences to less popular candidates, thus improving decentralization

- Numerical details on implementation

- The notion of epsilon-balanced weight vectors, and the star balancing algorithm. The corresponding impact on the inequality (min support >= max score). Adapting our current algorithm for a balanced weight vector, which is probabilistic and gives a guarantee on the approximation factor for the sum-of-squares objective, into a deterministic algorithm which gives a guarantee that, if $w_{nc}>0$ and edge $nc'$ exists, then $supp_w(c)/supp_w(c') <= 1+\eps $. Once we have it, we can compare our running time with the state of the art for star balancing: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.7945&rep=rep1&type=pdf (See theorem 1). Hopefully we have an algorithm that is faster, at least for bipartite graphs with one partition much smaller than the other.

- A generalization of the 3.15 approximation that deals with eps-balanced weight vectors. The current analysis considers that the weight vector is truly balanced. 

- Throughout the paper we're assuming that all operations take constant time (see our remark at the end of the preliminaries section). Maybe we should change this. In particular, the authors of the seq-Phragmen method (Brill et al.) warn that the denominators of the load function grow exponentially. Does our algorithm have the same problem? 

- An analysis of a greedy algorithm that executes our heuristic iteratively, without ever balancing the weight vector. We know it achieves PJR. It would be great if we can also prove it achieves a constant factor approximation, or more generally any other property that makes it better than seq-Phragmen and can be used as a selling point. It probably beats seq-Phragmen numerically, so we could add some tests. 

- Possibly a generalization of the problem with operators and multiplicities instead of validators. For more generality we can talk about political parties, but we should also mention the convenience for Polkadot in terms of network resilience in case some nodes drop out abruptly. 

- Possibly some results about how to reduce and encode solutions compactly for submission, and how to simultaneously get a reduced and verifiably PJR solution.